1. Field of the Invention
The present invention relates to an improved arithmetic unit and operating method, for effecting numerical calculations using interpolation, and more particularly to a high speed and small scale arithmetic unit and operating method, which are highly precise, through interpolation of a value referenced from a table followed by the Newton-Raphson operation.
2. Description of the Related Art
Perspective conversion and the normalization of normal vectors on screen are necessary in computer graphics. The calculations used in these processes, such as division, inverse, and inverse square root, include a large number of repetitive processes; for this reason, these calculations are performed with software and the amount of calculations becomes large, causing reduced performance of the entire system. In particular, pipeline systems, often used in computer graphics, are characterized by process flow without repetitive processes. Calculations with many repetitive processes do not work in a pipeline system.
Hardwiring these calculations, such as division, inverse, inverse square root, and the like, was considered as a way to raise processing speed. However, when circuits are not designed with efficient algorithms, circuits become large in scale. Possible problems include increased costs, increased temperatures due to heat during circuit operation, increased number of design steps, and increased human error.
The methods for calculations such as division and inverse of square root can be broadly classified as the "table reference method," "longhand method," and the "table reference plus Newton-Raphson repetition method." In the table reference method, for example, a table of inverse values is prepared for a limited domain of input values, the inverse value corresponding to the input value is referenced, and the result of the calculation is attained. In the table reference method, the number of sets of sampling values, picked up at prescribed intervals from a range of input values, and inverse values, corresponding to the sampling values, is limited. For this reason, the value closest to the actual input value is referenced from among the sampling values in the table. As a result, there is a discrepancy between the actual input value and the sampling value; this has an undesirable effect on the precision of the calculation results. Oppositely, the types of sampling values in the table must be increased to improve the precision of the calculation results and the table inevitably becomes large in scale.
The longhand method, in division for example, is the method of repeating the process of storing the results of subtracting the divisor (dividing number) from the dividend (number divided), moving the divisor one column to the right, and subtracting it again. The disadvantage is the long time necessary for attaining the results.
The table reference plus Newton-Raphson repetition method is the method for finding the results of the calculation with final precision by applying the Newton-Raphson operation repeatedly to an initial value determined by referencing the table. Details of the Newton-Raphson operation are explained here.
The Newton-Raphson operation is one solution for finding the root of the equation f(x)=0; FIG. 12 shows the principle of this solution. Specifically, for the curve y=f(x), an appropriate starting value x.sub.0 is used as the initial value, a vertical line is drawn from this x.sub.0, and the point P.sub.0 where the vertical line intersects the curve y=f(x) is found. Then a tangent to the curve is drawn at P.sub.0, and the point x.sub.1 where this tangent intersects the X axis is found. In the same way, a vertical line is drawn from x.sub.1, a point P.sub.1 where the vertical line crosses the curve y=f(x) is found, a tangent is drawn at this point P.sub.1, and the point x.sub.2 where the tangent intersects the x axis is found. This operation is repeated to find x.sub.1, x.sub.2, . . . , x.sub.i . . . ; x.sub.i gradually approaches, in effect converges upon, the root alpha of the formula f(x)=0. This type of calculating method is called a method of successive approximation.
Here, the equation for the tangent at P.sub.0 becomes EQU y=f'(x.sub.0) (x-x.sub.0)+f(x.sub.0)
if f(x) is differentiable. A formula for finding x.sub.1 is created from the equation of the tangent, but because x.sub.1 is an x intercept, y=0 when x=x.sub.1. When this is substituted in the equation for the tangent and x.sub.1 is found, then EQU 0=f'(x.sub.0) (x.sub.1 -x.sub.0)+f(x.sub.0) EQU x.sub.1 -x.sub.0 =f(x.sub.0)/f'(x.sub.0) EQU x.sub.1 =x.sub.0 -f(x.sub.0)/f'(x.sub.0)
To generalize this equation, x.sub.i and x.sub.i+1 are substituted for x.sub.0 and x.sub.1 respectively and the equation for finding x.sub.i+1 from x.sub.i is written as follows. EQU x.sub.i+1 =x.sub.i -f(x.sub.i)/f'(x.sub.i)
(i=0, 1, 2, . . . ) PA1 and therefore, the root for f(x)=0 is found. With the Newton-Raphson method , EQU x.sub.i+1 =x.sub.i -f(x.sub.i)/f'(x.sub.i) EQU =x.sub.i -(1/x.sub.i -A)/(-1/x.sub.i.sup.2) EQU =x.sub.i +x.sub.i -Ax.sub.i.sup.2 =x.sub.i -x.sub.i (Ax.sub.i -1)
The root of the equation f(x)=0 is found with the Newton-Raphson method by inputting an appropriate initial value for x0 and repeating the aforementioned calculation. Actually, when the equation f(x) is expressed using a constant A, Y=1/x becomes EQU f(x)=1/x-A
This final item -x.sub.i (Ax.sub.i -1) means that the error between the actual product and 1 is found and x.sub.i is revised according to the error, because the value x.sub.i found at that time is multiplied by the aforementioned constant A and this product properly becomes 1 if there is no error. Because of this repeated correction (revision) of the value using the final item -x.sub.i (Ax.sub.i -1), the final item -x.sub.i (Ax.sub.i -1) is called the correction.
In other words, the Newton-Raphson operation requires the calculation of the correction -x.sub.i (Ax.sub.i -1); but the correction can be calculated with a small scale calculation if the initial precision is close to the true value. Moreover, the Newton-Raphson operation recursively improves precision; the aforementioned Newton-Raphson repetition method therefore improves precision by applying the Newton-Raphson method once more to the x.sub.i+1 attained here. The aforementioned Newton-Raphson repetition method can be realized mathematically, but the circuits become extremely complex when this method is hardwired.
In the table reference plus Newton-Raphson repetition method, the initial value for the aforementioned Newton-Raphson operation is referenced from the table. In this case, the repetition of the Newton-Raphson operation can be reduced if the initial value is highly precise and close to the true value. For this reason, it is thought that the precision of the initial value attained from the table is improved and the repetition of the Newton-Raphson operation is reduced.
However, a problem is that the table becomes large in scale, as noted for the table reference method, in order to attain a precise initial value from the table. Also, when the repetition of the operation is hardwired, each repetition must have a corresponding portion of the circuit. For this reason, an increased circuit scale results from performing the Newton-Raphson operation two or more times. Furthermore, the repetition of the processes causes the problem of increasing the time difference (latency) from when the input value is provided output terminal the system to when the results are output.
Also, the sign of the aforementioned initial value used in the process of the Newton-Raphson operation varies because of the influence of error. A sign determination circuit is necessary for calculating a numerical value which may be positive or negative. This causes the problem of further increasing the complexity of the circuit.